package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/wiggle-subsequence/
 * @create 2025/9/8 20:10
 * @since JDK17
 */

public class Solution97 {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int[][] dp = new int[n][2];
        dp[0][0] = dp[0][1] = 1;
        dp[1][0] = nums[1] > nums[0] ? 2 : 1;
        dp[1][1] = nums[1] > nums[0] ? 1 : 2;
        for (int i = 2; i < n; i++) {
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {    // 正数
                    dp[i][0] = Math.max(dp[i][0], 1 + dp[j][1]);
                } else {    // 负数
                    dp[i][1] = Math.max(dp[i][1], 1 + dp[j][0]);
                }
            }
        }

        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}
